package com.sicheng.lc.周赛.分类.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/8 15:06
 */
@SuppressWarnings("all")
public class 使数组K递增的最少操作次数 {
    //https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/
    // 按 k 分组
    // nums[0] nums[k] nums[2k] nums[3k] ....
    // nums[1] nums[1+k] nums[1+2k] nums[1+3k] ....
    // nums[3] nums[3+k] nums[3+2k] nums[3+3k] ....
    // nums[k-1] nums[k-1+k] nums[k-1+2k] ....
    // 思维转换到最长不降子数组
    static int[] num = new int[(int) 1e5];
    // tails[i] 表示长度为i+1的最长递增子序列的最后一个元素
    // 要让tails[i]尽可能小这样才能更容易接上下一个元素
    static int[] tails = new int[(int) 1e5];
    int len = 0;

    public int kIncreasing(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < k; i++) {
            int n = 0;
            for (int j = i; j < nums.length; j += k) {
                num[n++] = nums[j];
            }
            res += longest(n);
        }
        return res;
    }


    private int longest(int n) {
        len = 0;
        for (int i = 0; i < n; i++) {
            // 遍历元素
            // 如果当前元素大于或等于就加入
            // 否则找到第一个大于num[i]的将其替换成num[i],tails是非减序的
            if (len == 0 || num[i] >= tails[len - 1]) {
                tails[len++] = num[i];
            } else if (num[i] < tails[len - 1]) {
                int l = 0, r = len - 1;
                while (l <= r) {
                    int mid = l + r >> 1;
                    if (tails[mid] >= num[i] + 1) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                tails[l] = num[i];
            }
        }
        return n - len;
    }

    public static void main(String[] args) {
        使数组K递增的最少操作次数 s = new 使数组K递增的最少操作次数();
        int[] nums = {4, 1, 5, 2, 6, 2};
        int k = 2;
        System.out.println(s.kIncreasing(nums, k));
    }
}
